// 方法一：左闭右闭
function binarySearch(arr, target) {
  let left = 0;
  // 包含右边界
  let right = arr.length - 1;
  while (left <= right) {
    /**
     * 注意点：
     * 常规方法：mid = (left + right) / 2;
     * 当left和right非常大，接近于2^53，会超出范围，需要避免大数溢出
     *
     * 解决办法：
     * 1.位运算优化
     * mid = left + ((right - left) >> 1); 右移一位（等价于除以 2）
     * 计算差值，右移一位，left加上偏移量
     * 2.中间值向上取整
     * mid = left + Math.floor((right - left) / 2);
     * Math.floor 能正确处理浮点数。
     */
    let middle = Math.floor((left + right) / 2);
    if (arr[middle] < target) {
      left = middle + 1;
    } else if (arr[middle] > target) {
      right = middle - 1;
    } else {
      return middle;
    }
  }
  return -1;
}
// 方法二：左闭右开
// function binarySearch(arr, target) {
//   let left = 0;
//   //不包含右边界
//   let right = arr.length;
//   while (left < right) {
//     let middle = Math.floor((left + right) / 2);
//     if (arr[middle] > target) {
//       right = middle;
//     } else if (arr[middle] < target) {
//       left = middle + 1;
//     } else {
//       return middle;
//     }
//   }
//   return -1;
// }
const arr = [1, 2, 3, 4, 5, 6, 7];
const target = 6;
const res = binarySearch(arr, target);
console.log(res);
